题目分析

这个题目有难度，可能理解起来都比较困难。题目我是读了好久，然后样例也是迷迷糊糊不太清晰，应该多给出一些样例。不明白的小伙伴可以看我的分析，然后自己实现。

队列+贪心

我最后理解了题意，这个问题是不会平局的，如果第一次没有结束，那么剩余的人还会进行第二次投票。
举个例子，”RRDDD”这个例子，一开始我的理解是平局，因为前面两个R会禁赛前面两个D，最后一个D会禁赛第一个R。因此只有一个R和一个D有投票权，因此平局。但是没有平局的输出，看了评论区和题解才明白，这时的顺序是R和D，因为第一个R和前两个D没有投票权，相当于踢出场外，剩下的是RD，继续投票，R会禁赛D，因此R胜利。

小伙伴们看了上面的分析能否写出这个题目呢？

这里用到了贪心的思路，我们都想胜利，那么如何做才能最优呢？我们要封禁即将要投票的对手，这是最优解，这样我们才能更好的保护我们的队员。如RDRD，第一个R要优先封印第一个D，将第一个D踢出场外，这样第二个R才不会被踢出场外。

我们按照顺序将R和D分成两排，其中存储着所在位置的索引。比较两个队头元素哪一个小，说明哪一个有优先封印权，然后封印另一个队列的第一个元素。被封印的元素踢出场外，使用封印权的元素加到队列末尾。因为进入了下一轮，因此索引要+n，确保一定比上一轮的所有元素的索引都要大。等到哪一个队伍的元素都被踢出，则另一个队伍胜利。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<deque>

using namespace std;

class Solution {
public:
    string predictPartyVictory(string senate) {
        deque<int> R, D;
        int n = senate.size();
        for (int i = 0; i < senate.size(); i++) {
            senate[i] == 'R' ? R.push_back(i) : D.push_back(i);
        }
        while (!R.empty() && !D.empty()) {
            R.front() < D.front() ? R.push_back(R.front() + n) : D.push_back(D.front() + n);
            D.pop_front();
            R.pop_front();
        }
        return R.empty() ? "Dire" : "Radiant";
    }
};

刷题总结

博弈的题目都比较有意思，博弈题在这里总结一下，往往都有3个思路，一个是动态规划，要求解最后问题的最优解，我们先看子问题的最优解。另一个是贪心，如果当前最优就是全局最优，就可以使用贪心。最后一个是数学，有的博弈问题可以用数学公司或者数学思路求解，这个难度也是最大的。希望小伙伴们遇到这种问题能够想到这三个思路。